package com.jack.leetcode.test;

import java.util.Arrays;

public class 数的平方等于两数乘积的方法数 {

    public static void main(String[] args) {
        int[] a ={1, 1};
        int[] b ={1, 1, 1};
        System.out.println(numTriplets(a, b));
        int[] c = {1,3,1,2};
        int[] d = {2,3,5,3,2};
        System.out.println(numTriplets(c, d));
        int[] e = {43024,99908};
        int[] f = {1864};
        System.out.println(numTriplets(e, f));
        int[] g = {7, 7, 8, 3};
        int[] h = {1, 2, 9, 7};
        System.out.println(numTriplets(g, h));
    }

    public static int numTriplets(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int m = nums1.length;
        int n = nums2.length;
        int result = 0;
        int[] dp1 = new int[m];
        //类型1
        for(int i = 0;i < m;i++){
            long cur = (long)nums1[i] * nums1[i];
            for(int j = 0;j < n - 1;j++){
                for(int k = j + 1;k< n;k++){
                    long tmp = (long)nums2[j] * nums2[k];
                    if(tmp == cur){
                        result++;
                        while(i < m - 1 && nums1[i] == nums1[i+1]){
                            i++;
                            result++;
                        }
                        while(k < n - 1 && nums2[k] == nums2[k+1]){
                            k++;
                            result++;
                        }
                    }else if(tmp > cur){
                        break;
                    }
                }
            }
        }
        //类型2
        for(int i = 0;i < n;i++){
            long cur = nums2[i] * (long)nums2[i];
            for(int j = 0;j < m - 1;j++){
                for(int k = j + 1;k< m;k++){
                    long tmp = (long)nums1[j] * nums1[k];
                    if(tmp == cur){
                        result++;
                        while(i < n - 1 && nums2[i] == nums2[i+1]){
                            i++;
                            result++;
                        }
                        while(k < m - 1 && nums1[k] == nums1[k+1]){
                            k++;
                            result++;
                        }
                    }else if(tmp > cur){
                        break;
                    }
                }
            }
        }
        return result;
    }
}
